package offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/1/20
 **/
public class Flatten {
    public void flatten(TreeNode root){
        List<TreeNode> ans = new ArrayList<>();
        recPreOrderTraversal(ans,root);
        ans.stream().forEach(node->node.left=null);
        for (int i = 0; i < ans.size()-1; i++) {
            ans.get(i).right = ans.get(i+1);
        }
        return;
    }
    public void recPreOrderTraversal(List<TreeNode> ans, TreeNode root){
        if(root == null){
            return;
        }
        ans.add(root);
        recPreOrderTraversal(ans,root.left);
        recPreOrderTraversal(ans,root.right);
    }

    public void o1SpaceFlatten(TreeNode root){
        TreeNode current, rightMost;
        if(root == null){
            return;
        }
        current = root;
        while(current != null){
            if(current.left == null){
                current = current.right;
            }else{
                rightMost = current.left;
                while(rightMost.right != null && rightMost.right != current){
                    rightMost = rightMost.right;
                }
                if(rightMost.right == null){
                    rightMost.right = current;
                    current = current.left;
                }else{
                    rightMost.right = null;
                    current = current.right;
                }
            }


        }

    }

}
